package sortAlgorithm;

import java.util.Arrays;

public class HeapSort {
    public static void main(String[] args) {
        int[] a = {8, 5, 10, 7, 4, 9, 7, 2, 23};
        heapSortDown(a);
        System.out.println(Arrays.toString(a));
        heapSortUp(a);
        System.out.println(Arrays.toString(a));
    }

    /***
     * 由小到大
     * @param array 待排数组
     */
    public static void heapSortUp(int[] array) {
        makeMaxHeap(array);
        for (int i = array.length - 1; i >= 0; i--) {
            int temp = array[i];
            array[i] = array[0];
            array[0] = temp;
            maxHeapFixDown(array, 0, i);
        }
    }

    /***
     * 由大到小
     * @param array 待排数组
     */
    public static void heapSortDown(int[] array) {
        makeMinHeap(array);
        for (int i = array.length - 1; i >= 0; i--) {
            int temp = array[i];
            array[i] = array[0];
            array[0] = temp;
            minHeapFixDown(array, 0, i);
        }
    }

    /**
     * 堆化为小顶堆
     *
     * @param array 待堆化数组
     */
    private static void makeMinHeap(int[] array) {
        for (int i = array.length / 2; i >= 0; i--) {
            minHeapFixDown(array, i, array.length);
        }
    }

    /**
     * 堆化为大顶堆
     *
     * @param array 待堆化数组
     */
    private static void makeMaxHeap(int[] array) {
        for (int i = array.length / 2; i >= 0; i--) {
            maxHeapFixDown(array, i, array.length);
        }
    }

    /**
     * 调整为小顶堆
     *
     * @param array  待堆化数组
     * @param i      要堆化二叉树最上层节点下标
     * @param length 堆化的末元素下标或数组长度
     */
    private static void minHeapFixDown(int[] array, int i, int length) {
        int j = 2 * i + 1;
        int temp = array[i];
        while (j < length) {
            if (j + 1 < length && array[j + 1] < array[j]) {
                j++;
            }
            if (array[j] < temp) {
                array[i] = array[j];
                i = j;
                j = 2 * i + 1;
            } else {
                break;
            }

        }
        array[i] = temp;
    }

    /**
     * 调节为大顶堆
     *
     * @param array  待堆化数组
     * @param i      要堆化二叉树最上层节点下标
     * @param length 堆化的末元素下标或数组长度
     */
    private static void maxHeapFixDown(int[] array, int i, int length) {
        int j = 2 * i + 1;
        int temp = array[i];
        while (j < length) {
            if (j + 1 < length && array[j + 1] > array[j]) {
                j++;
            }
            if (array[j] > temp) {
                array[i] = array[j];
                i = j;
                j = 2 * i + 1;
            } else {
                break;
            }
        }

        array[i] = temp;
    }
}
